<?php

/*
  Copyright 2010 Mark Watkinson

  This file is part of Luminous.

  Luminous is free software: you can redistribute it and/or
  modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  Luminous is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with Luminous.  If not, see <http://www.gnu.org/licenses/>.

*/

require_once('luminous_grammar.class.php');
require_once('luminous_rule.class.php');


/**
 * \file luminous_luminous.class.php
 *  
 * \brief The central luminous class and a few utility functions.
 * 
 * \defgroup LuminousUtils LuminousUtils
 * A set of ulities used by the Luminous class.
 * \internal
 */ 


/**
 * \ingroup LuminousUtils
 * \internal
 * \brief Decodes a PCRE error code into a string
 * \param errcode The error code to decode (integer)
 * \return A string which is simply the name of the constant which matches the
 *      error code (e.g. 'PREG_BACKTRACK_LIMIT_ERROR')
 */ 
function pcre_error_decode($errcode)
{
  switch ($errcode)
  {
    case PREG_NO_ERROR:
      return 'PREG_NO_ERROR';
    case PREG_INTERNAL_ERROR:
      return 'PREG_INTERNAL_ERROR';
    case PREG_BACKTRACK_LIMIT_ERROR:
      return 'PREG_BACKTRACK_LIMIT_ERROR';
    case PREG_RECURSION_LIMIT_ERROR:
      return 'PREG_RECURSION_LIMIT_ERROR';
    case PREG_BAD_UTF8_ERROR:
      return 'PREG_BAD_UTF8_ERROR';
    case PREG_BAD_UTF8_OFFSET_ERROR:
      return 'PREG_BAD_UTF8_OFFSET_ERROR';
    default:
      return 'Unknown error code';
  }
}

/**
 * \ingroup LuminousUtils
 * \internal
 * \brief Simple string replace equivalent to preg_replace_callback
 * A string replace, which uses for the replacement a series of (individual)
 * calls to a callback function.
 * \param needle the search string
 * \param callback the callback function whose return shall be used as the 
 *  replacement. It shall receive exactly 1 argument, which is the search 
 *  needle. It will be called for every match, so if its output changes that 
 * will be caught by this function.
 * 
 * It must be callable by call_user_func. For references to an object,
 *  use array($obj, "methodName"). Otherwise use "funcname"
 * \param haystack the string in which to search and replace
 * \return the input string (haystack) with necessary replacements made
 */ 

function str_replace_callback($needle, $callback, $haystack)
{
  $index = -1;
  $last_index = 0;
  $str = "";
  $strlen_needle = strlen($needle);
  while( ($index = strpos($haystack, $needle, $index+1)) !== false)
  {
    $str .= substr($haystack, $last_index, $index-$last_index);
    $str .= call_user_func($callback, $needle);
    $last_index = $index + $strlen_needle;
  }
  $str .= substr($haystack, $last_index);
  return $str;  
}



/**
 * \ingroup LuminousUtils
 * \internal
 * \brief Determines if a character in a string is escaped.
 * Determines if a string index is an escaped character according to the given
 *      escape characters
 * \param str The string as a whole (or at least, up to and including index)
 * \param index the string index of the character to check
 * \param slashchars an array of legal escape characters (i.e. a backslash)
 * \return true|false
 *
 */ 
function is_escaped(&$str, &$index, array &$slashchars)
{
  $i = $index-1;
  
  // minor optimisation, but this function gets bombarded so much...
  if (isset($slashchars[1]))
  {
    while (($i >= 0) && in_array($str[$i], $slashchars))
      --$i;
  }
  elseif (isset($slashchars[0]))
  {
    $c = $slashchars[0];
    while (($i >= 0) && $str[$i] === $c)
      --$i;    
  }
  else
    return false;
  
  return (($index - $i - 1) & 1) === 1;  
}

/**
 * \ingroup LuminousUtils
 * \internal
 * \brief Matches a start-delimiter to an end-delimiter.
 * 
 * 
 * 
 * Matches a start delimiter to an end delimiter for the purpose of dynamic 
 * delimiter definitions. This usually means the funciton returns the start
 * delimiter it is given, but will match up open brackets  to close brackets 
 * and so forth. If the delimiter is to be used in a regex, it will be 
 * escaped as necessary.
 * 
 * \param delim the starter delimiter (character)
 * \param regex Set to true if the delimiter going to be used in a regex, false 
 *      otherwise (default: true)
 * 
 * \return The corresponding ending delimiter.
 * 
 * \todo complete the list for all regex unsafe chars.
 * 
 * 
 */ 
function match_delimiter($delim, $regex=true)
{
  $e = '';
  $esc = false;
  switch($delim)
  {
    case '(':         
      $e = ')';
      $esc = true;
      break;
    case '{': $e = '}';
      $esc = true;
      break;
    case '[': $e = "]";
      $esc = true;
      break;
    case '&lt;': $e = '&gt;';
      break;
    case '/':
    case '?':  
    case '+':
    case '*':
    case '.':  
    case '$':
    case '^':
    case '-':
    case '|':
      $e = $delim;   
      $esc = true;
      break;
    
    default:
      $e = $delim;
  }
  
  if ($regex && $esc)
  {
    $e = "\\$e";
  }
  return $e;
}

function tag_lines(&$tag, &$lines)
{
  $lines = str_replace("\n", '</' . $tag . ">\n<" . $tag . '>', $lines);
  $lines = '<' . $tag . '>' . $lines . '</' . $tag . '>';
}


/**
 * \class Luminous
 * 
 * \brief Luminous is an automaton which handles source code highlighting.
 * 
 * This is what it's all centred around.
 * Luminous works by taking an input string and a LuminousGrammar and then
 * applying the rules in the grammar to the string. Luminous::Parse_Full is
 * the method to see for the high level.
 * 
 * Roughly speaking there are two phases to this process. The first is to filter
 * out delimited types, which is done by traversing the string. 
 * 
 * After that, simple types are matched by spamming regular expression matches
 * at what's left.
 * 
 * 
 * But it's all a bit convoluted because of a various optimisations to keep
 * the process fast enough to be useful.
 * 
 * Anything that matches at any point is pushed into the 
 * Luminous::html_extractions array and a placeholder alias is inserted into the
 * string at its index. This makes it unmatchable by any other rule, so never 
 * should a string be highlighted inside a comment, or similar.
 * 
 * Nested languages are handled from the bottom up: any language which nests 
 * inside another but has none inside itself should be called first. It removes
 * any of itself from the string, then passes what remains down to another
 * instance of Luminous with the grammar's LuminousGrammar::child_grammar. 
 * 
 * \see Luminous::ParseDelimiters 
 * \see Luminous::ParseRegex
 * 
 * \todo Some of these methods are missing documentation.
 * 
 * \warning don't re-use luminous objects. 
 * 
 */

class Luminous
{
  /** Config options */
  
  /// See: \ref verbosity
  public $verbosity = 4;
  
  /**
   * Sets whether or not the input is already HTML entity escaped
   * \since 0.30
   */ 
  public $pre_escaped = false;

  
 
  /**
   * Not yet supported
   * \todo this.
   */  
  public $lang_specific_classnames = false;
  
  public $language = null;
  
  
  
  
  
  
  private $input_src = ""; /**< Input - a source string */
  private $output = ""; /**< Output - a tagged source string */
  private $grammar; /**< Grammar - langauge rules */

  /** State related data */
  private $index = 0; /**< The input string pointer */
  private $open_tag = null; /**< The currently open delimiter */
  private $open_index = null; /**< Index of the currently open delimiter */
  private $open_delim_len = null; /**< Length of the currently open delimiter */
  private $close_delim = null; /**< The corresponding closing delimiter which is being  
      searched for */
  private $long_delim = false; /**< In the case of dynamically delimited types,
    this specifies whether the delimiter is a single char or a long alphanumeric
    string */

  /** Extractions/aliasing data */
  private $html_extractions = array(); /**< Alias to representation lookup */
  private $html_extractions_tags = array(); /** index to tag lookup */  
  
  private $html_extractions_langs = array();

  private $num_extractions = 0; /// Number of extractions (aliases) performed 
  private $extractions_offset = 0;  /**< Alias ID to start at (so as not to 
    collide with existing alises from other parsers */
  

  private $callback_data = null; /**< Somewhere to put data to be accessible 
    from a callback function whose arg list does not allow passing it */
  private $callback_data2 = null; ///sometimes one just isn't enough.
   
  /// Luminous sticks a newline at the end of the string is none exists, 
  /// we record here whether we need to remove it again afterwards.
  private $append_newline = false;

  /** Optimisations */
  private $starts = array(); /// indices of possible start tags.
  private $ends = array(); /// indices of possible end tags
  private $ends_length = array(); /// lengths of end tags (references $ends)
  private $ends_excludes = array(); /// Which end tags should be excluded
  private $num_ends = 0; /// count($this->ends)
  
  ///regex search cached results (pattern=>index)
  private $regex_search_cache = array();
  private $strpos_cache = array();  /// strpos search cache (str=>index).
  
  private $last_str_index_gne = 0; 
  private $last_arr_index_gne = 0;

  private $last_str_index_gns = 0;
  private $last_arr_index_gns = 0;

  /// indices of existing replacements. (from a parent grammar)
  private $existing_replacements = array();

  /// true if there are no ignore tags to worry about
  private $parse_all = false;
  
  /// count($this->grammar->escape_chars)
  private $num_escape_chars = 0;
  
  /// Tries to avoid unnecessary calls to is_escaped
  private $escape_cache = array();
  
  /**
   * delimiter rules from the grammar are copied here so the array can be 
   * changed, as a non-hit of a rule anywhere in the string means it's best to 
   * remove it so we won't iterate over it again
   */ 
  private $local_rules = array();
  private $local_simple_types = array();
  
  /////////////////////////////////////////////////////////////////////////////
  /// SKELETAL STATE CODE. NOT YET IN USE.
  private $state_rules = array();
  private $local_rules_for_state = array();  
  
  /// Stack of states
  private $state = array();
  private $use_states = false;
  
  private function PushState($state)
  {
    array_push($this->state, $state);
    $this->local_rules_for_state = $this->state_rules[$state];
  }
  private function PopState()
  {
    array_pop($this->state);
  }
  /////////////////////////////////////////////////////////////////////////////
  



  
  /**
   * Constructor. Nothing interesting here.
   * \param src the source string (optionally set this later with 
   *    SetSource)
   * \see Luminous::SetSource
   */ 
  function __construct($src = null)
  {
    if ($src != null)
      $this->input_src = $src;
  }
  
  /**
    * Sets the input source string
    * \param src the string of source code to parse
    */
  public 
  function SetSource($src)
  {
    $this->input_src = $src;
  }

  /**
   * \internal
   * Sets the extraction offset to start at.  This is for recursive calls on
   * the same string,  so that different parser objects do not collide and
   * overwrite each other's changes with their own
   * \param num The base number to start from.
   */

  public 
  function SetExtractionsOffset($num)
  {
    $this->extractions_offset = $num;
  }

  /**
   * Sets Luminous's grammar
   * \param grammar the LuminousGrammar object
   */

  public 
  function SetGrammar(LuminousGrammar $grammar)
  {
    $this->grammar = $grammar;
    $this->grammar->SetRuleset($this->input_src);
    $this->num_escape_chars = count($this->grammar->escape_chars);
    $this->local_rules = $grammar->delimited_types;
    $this->local_simple_types = $grammar->simple_types;
    
    foreach($this->local_simple_types as $k=>$r)
    {
      if ($r->verbosity > $this->verbosity)
        unset($this->local_simple_types[$k]);
    }
    foreach($this->local_rules as $k=>$r)
    {
      if ($r->verbosity > $this->verbosity)
        unset($this->local_rules[$k]);
    }    
    
    if (isset($this->grammar->info['language']) && 
      strlen($this->grammar->info['language']))
      $this->language = strtoupper($this->grammar->info['language']);
    else
      $this->language = "oops";
  }


  


  /**
   * Determines if a character at a given index is escaped or not
   *  \param index the index of the character. If null, the current $this->index
   * is used
   *  \return true or false
   */
  private 
  function CharIsEscaped($index=null)
  {
    $index = ($index !== null)? $index : $this->index;
    if (isset($this->escape_cache[$index]))
      return $this->escape_cache[$index];
    
    $e = is_escaped(
      $this->input_src, 
      $index,
      $this->grammar->escape_chars);
    $this->escape_cache[$index] = $e;
    return $e;
  }
  


  /**
   * Adds a 'replacement' to the internal data. The given string isreplaced by
   * some pattern, and the alias lookup stored internally
   * \param replacement the string to be replaced
   * \param tag the type (tag) of the data which is being stored. This may be 
   *    null but if the data is all of one type, it really shouldn't be.
   * \return the alias which now represents the string.
   */

  public 
  function AddReplacement($replacement, $tag = null)
  {
    $i = $this->num_extractions+$this->extractions_offset;
    $pattern = '<&R_' . $i . '>';
    if ($tag !== null)
    {
      $this->html_extractions_tags[$i] = $tag;
      tag_lines($tag, $replacement);
    }
    $this->html_extractions[$i] = $replacement;
    
    $this->html_extractions_langs[$i] = $this->grammar->info['language'];
    
    $this->num_extractions++;
    return $pattern;
  }
  
  
  
  private 
  function DoNestedReplacements(&$rule, $start, $end)
  {
    $c = &$rule->callback;
    $t = &$rule->name;
    $i = $start;
    
    $r = $this->Get_Next_Replacement($i);      
    if ($r !== null && $r <= $end)
    {
      $substr = substr($this->input_src, $start, $end-$start);
      
      
      while( ($r !== null && $r < $end) )
      {        
        $rep_end = strpos($this->input_src, '>', $r)+1;
        $substr = substr($this->input_src, $i, $r-$i);
        
        if ($c !== null  && $this->verbosity >= 3)
          $c($substr);
        $this->output .= $this->AddReplacement($substr, $t);
        $substr = substr($this->input_src, $r, $rep_end-$r);
        $this->output .= $substr;
        $i = $rep_end;
        $r = $this->Get_Next_Replacement($i);  
        
        if($r === null || $r > $end)
        {
          $substr = substr($this->input_src, $rep_end, $end-$rep_end);
          if ($c !== null)
            $c($substr);
          $this->output .= $this->AddReplacement($substr, $t);
        }
      }
    }
    
    else
    {
      $substr = substr($this->input_src, $start, $end-$start);
      
      if ($c !== null && $this->verbosity >= 3)
        call_user_func_array($c, array(&$substr));
      $this->output .= $this->AddReplacement($substr, $t);
    }    
  }
  
  /**
   * \param match_txt the text of the next match
   * \return the index of the next matching delimiter for the given rule_text
   */
  private function GetNextEndDelim(&$rule, &$match_txt)
  {
    
    $rule_type = &$rule->type;
    
    
    $end = false;
    $index = $this->open_index+$this->open_delim_len;
    $found = true;
    
    do
    {
      $found = true;
      $end = 0;
      if ($rule_type & LUMINOUS_REGEX)
      {
        $m = array();
        if ($this->grammar->case_insensitive === true)
          $this->close_delim .= 'i';
        
        if (!preg_match($this->close_delim, $this->input_src, $m, PREG_OFFSET_CAPTURE,
          $index))        
          $end = false;
        else
        {
          $m0 = &$m[0];
          $end = $m0[1];
          $match_txt = $m0[0];          
        }
      }
      else
      {        
        $strpos = ($this->grammar->case_insensitive)?'stripos' : 'strpos';
        $end = $strpos($this->input_src, $this->close_delim, $index);
        $match_txt = $this->close_delim;
      }
      
      if($end!== false && $this->CharIsEscaped($end))
      {
        $found = false;
        $index = $end+1;
        if ($index >= strlen($this->input_src))
          break;
      }
    }
    while(!$found);
    return $end;
  }

  
  /**
   * Finds the corresponding ending delimiter to the currently open starting
   * delimiter.
   * It also completes the process of extracting a delimited type and moves the
   * input pointer along appropriately.
   */
  private 
  function DoEndingDelim(&$rule, $end=false)
  {
    $rule_type = &$rule->type;    

    $match_txt = "";
    
    if ($end === false)
      $end = $this->GetNextEndDelim($rule, $match_txt);
    if ($end === false)
      $end = strlen($this->input_src);
    
    $stop_at_end = ($rule_type & LUMINOUS_STOP_AT_END);    
    $stopping_at_end = false;
    if ($stop_at_end)
    {
      $close = $this->Get_Next_End($this->open_index);
      if ($end === false || ($close !== null && $close <= $end) )
      {
        $end = $close;

        if (
          !$this->ends_excludes[$close])
        {
          $end -= $this->ends_length[$close];
          
          // This is probably not the right way to handle this situation
          // there might be a bug elsewhere that causes this to happen.
          $end = max($this->open_index+1, $end);
        }
        $stopping_at_end = true;
      }
    }
    

    $match_len = strlen($match_txt);
    
    $t = strtoupper($this->open_tag);

    if (!$stopping_at_end && !($rule_type & LUMINOUS_EXCLUDE))
      $end += $match_len;
    $this->DoNestedReplacements($rule, $this->open_index, $end);

    if ($rule_type & LUMINOUS_EXCLUDE)
    {
      $this->output .= $this->AddReplacement(substr($this->input_src, $end, $match_len));
      $end += $match_len;        
    }

    $this->index = $end;
    return true;
  }

  /**
   * Determines if a given character is a separating character, or if it may be
   * a name of a variable, or something
   */
  private 
  function IsSeparatorChar($c)
  {
    if (ctype_alnum($c))
      return false;
     if ($c == "_")
       return false;

    return true;
  }



  /**
   * Escapes the input string to make it suitable for processing.
   * This should be called once and only once on any input. Child grammars 
   * shouldn't escape the string again.
   */
  public 
  function EscapeInput()
  {
    
    $this->input_src = str_replace("&", "&amp;", $this->input_src);
    $this->input_src = str_replace(">", "&gt;", $this->input_src);
    $this->input_src = str_replace("<", "&lt;", $this->input_src);
    
    // DOS line endings
    $this->input_src = str_replace("\r\n", "\n", $this->input_src);
    
    // Mac line endings?
    $this->input_src = str_replace("\r", "\n", $this->input_src);
    
    if (strlen($this->input_src) && $this->input_src[strlen($this->input_src)-1]
      != "\n")
    {
      $this->input_src .= "\n";
      $this->append_newline = true;
    }

  }


  private 
  function GetStartDelim(&$match_rule, &$s_delim)
  {    
    $next = -1;    
    $this->input_src;
    $strpos = ($this->grammar->case_insensitive)?'stripos' : 'strpos';        
    foreach ($this->local_rules as $key=>&$rule)
    {
      
      $type = &$rule->type;        
      $opener = &$rule->delim_1;
      $rule_text = $rule->delim_1;
      $r = -1; // index of the next match.
      
      // start figuring out where the next match is.
      
      if(!($type & LUMINOUS_REGEX)) // simple strpos search.
      {
        
        if (isset($this->strpos_cache[$opener]))
        {
          $r = $this->strpos_cache[$opener];
          if ($r === false)
          {
            unset($this->local_rules[$key]);
            continue;
          }
        }
        if ($r < $this->index)
        {
          
          $r = $strpos($this->input_src, $opener, $this->index);
          if ($r === false)
          {
            unset($this->local_rules[$key]);
            
            continue;          
          }
          $this->strpos_cache[$opener] = $r;
        }
      }
      else // regex.
      {
        $match = null;
        if ($this->grammar->case_insensitive === true)
          $opener .= 'i';
        
        if (isset($this->regex_search_cache[$opener]))
        {
          $a = $this->regex_search_cache[$opener];
          $r = $a[0];
          if ($r === false)
          {
            unset($this->local_rules[$key]);
            
            continue;          
          }
          $match = $a[1];          
        }
        
        if ($r < $this->index)
        {
          $m = array();

          if (!preg_match($opener, $this->input_src, $m, PREG_OFFSET_CAPTURE, $this->index)
             )
          {
            $this->regex_search_cache[$opener] = array(false);
            unset($this->local_rules[$key]);
            continue;
          }
          
          $r = $m[0][1];
          $match = $m[0][0];
          $a = array($r, $match);
          $this->regex_search_cache[$opener] = $a;
        }        
        $rule_text = $match;
      }
      // end figuring out where the next match is.
      

      if ($r == -1) // no match.
          continue;

      if ($next == -1 || $r < $next)
      { 
        $next = $r;
        $s_delim = $rule_text;
        $match_rule = $rule;
        if ($next == $this->index)
        {
          return $next;
        }
      }
    }
    
    return $next;
    
  }

  

  /**
   * Parses delimited types according to the grammar rules
   */
  private 
  function ParseDelimiters()
  {

    $strlen = strlen($this->input_src);
    $this->index = 0;
    $last_end = -1;

    if(count($this->starts))
      $this->index = $this->starts[0];

    $this->output = substr($this->input_src, 0, $this->index);
    
    $this->output .= "<&START>";

    $start_open = true;

    $regex_search_cache = array();
    $strpos_cache = array();
    $use_cache = true;
    
    $last_index = $this->index-1;
    
    while ($this->index < $strlen)
    {
      if ($this->index <= $last_index)
      {
        die("Looks like the parser hit an infinite loop. This shouldn't have happened.");
      }        
      
      $last_index = $this->index;
      
      $next = $strlen;
      $s_delim = null;
      $e_delim = null;
      $open_tag = null;
      
      $next = $this->GetStartDelim($rule, $s_delim);
      
      // Don't parse the delimiters if it comes after an 'END'
      if (!$this->parse_all)
      {
        $e = $last_end;
        if ($e !== null && $e <= $this->index)
        {
          $e = $this->Get_Next_End();
          $last_end = $e;
        }        
        if ($e !== null 
          && ($e <= $next || $next == -1))
        {
          $s = substr($this->input_src, $this->index, $e-$this->index);
          $this->output .= "$s<&END>";
          $this->index = $e;
          $st = $this->Get_Next_Start($e);
          $start_open = false;
          if ($st !== null)
          {
            $s = substr($this->input_src, $e, $st-$e);
            $this->output .= "$s<&START>";
            $this->index = $st;
            $start_open = true;
            continue;
          }
          else
          {
            $this->output .= substr($this->input_src, $this->index);
            break;
          }
        }
      }
      
      if ($next >= $strlen || $next < 0)
      {
        $this->output .= substr($this->input_src, $this->index);
          break;
      }
      // trim whitespace from the start of the match, which prevents 
      // 'background colour' highlighting from bleeding on a rule which may have
      // had to specify whitespace as a captured match due to fixed-length 
      // lookbehind assertions
      if (strlen($s_delim) && ctype_space($s_delim[0]))
      {
        $t = ltrim($s_delim);
        $dist = strlen($s_delim) - strlen($t);
        $s_delim = $t;
//         $this->output .= substr($this->input_src, $this->index, $dist);
        $next += $dist;
      }
      
      $next_rule_type = $rule->type;
      $next_rule_name = $rule->name;
      $e_delim = $rule->delim_2;
      $open_tag = $rule->name;
      $this->long_delim = false;
      
//       echo "DELIM: $s_delim\n";          
      
      if ($next_rule_type & LUMINOUS_DYNAMIC_DELIMS)
      {
        $dyn_delim = $this->input_src[$next+strlen($s_delim)];
        
        // don't split entities
        if($dyn_delim === '&')
        {
          preg_match('/^&[^;]+;/', 
            substr($this->input_src, $next+strlen($s_delim)), $m_);
          $dyn_delim = $m_[0];
        }
        
        elseif (ctype_alnum($dyn_delim) || $dyn_delim === '_')
        {
          
          preg_match('/^[a-zA-Z_0-9]+/', 
            substr($this->input_src, $next+strlen($s_delim)), $m_);
          $dyn_delim = $m_[0];
        }
        
      }
      
      // if we get to here we're parsing the delimiters.
        
      $success = false;
      
      // complete match, no need to search for an ending.
      if (($next_rule_type & LUMINOUS_COMPLETE)
        && !($next_rule_type & LUMINOUS_DYNAMIC_DELIMS))
      {
        $this->output .= substr($this->input_src, $this->index, 
          $next-$this->index);
        $this->open_index = $next;
          
//         $this->DoEndingDelim($rule, $next + strlen($s));
        
        $s = strlen($s_delim);
        $this->DoNestedReplacements($rule, $next, $next+$s);
        
        $this->index = $next + $s;
        
        $success = true;
      }
      // uh oh
      else
      {
        if ($next_rule_type & LUMINOUS_DYNAMIC_DELIMS)
        {
          $s_delim .= $dyn_delim;
          
          if ($next_rule_type & LUMINOUS_REGEX)
          {
            $e = match_delimiter($dyn_delim, true);
            
            if ($next_rule_type & LUMINOUS_COMPLETE)
              $e_delim = "/$e/";
            else
              $e_delim = "/($e)$e_delim";
          }
          else
            $e_delim = match_delimiter($dyn_delim, false);
        }
        
        $s = substr($this->input_src, $this->index, ($next)-$this->index);
        
        $this->output .= $s; 
        if ($this->CharIsEscaped($next))
        {
          $this->index = $next+1;
          continue;
        }
        
        $this->open_delim_len = strlen($s_delim);
        
        if ($next_rule_type & LUMINOUS_EXCLUDE)
        {
          $inc = strlen($s_delim);
          $this->output .=  $this->AddReplacement(substr($this->input_src, $next, $inc));          
//          
          $next += $inc;
          $this->open_delim_len = 0;
        }
        
        $this->index = $next;
        $this->open_tag = $next_rule_name;
        $this->open_index = $next;
        
        $this->close_delim = $e_delim;
        
        if (!$this->DoEndingDelim($rule))
        {
          $this->output .= $this->input_src[$this->index];
          $this->index = $next+1;
        }
        else
          $success = true;
      }
      if ($success)
      { 
        if ($next_rule_type & LUMINOUS_END_IS_END)
        {
          $this->output .= '<&END>';
          $start_open = false;
          
          $st = $this->Get_Next_Start($this->index);
      
          if ($st !== null)
          {
            $s = substr($this->input_src, $this->index, $st-$this->index);
            $this->output .= "$s<&START>";
            $this->index = $st;
            $start_open = true;
            continue;
          }
          else
          {
            $this->output .= substr($this->input_src, $this->index);
            break;
          }
        } 
      }
    }

    if ($start_open)
      $this->output .= "<&END>";


  }


  /**
   *    Callback function for a preg_replace_callback in ParseRegex()
  */
  private 
  function Parse_Regex_Replace_Callback($matches)
  {     
    // need to exclude <>s
    $s = "";
    
    $group_no = &$this->callback_data2->group;
    if (!isset($matches[$group_no]))
    {
      trigger_error("Grammar error {$this->grammar->info['language']}: No such captured group '$group_no' in rule 
      {$this->callback_data2->name}");
      return $matches[0];
    }
    $g = &$matches[$group_no];
    
    
    if ($this->extractions_offset && preg_match_all("/<&R_[0-9]+>/",
      $matches[0], $m, PREG_OFFSET_CAPTURE))
    {
      $l = 0;
      foreach($m as &$match)
      {
        $group = $match[0][0];
        $offset = $match[0][1];
        $strlen = strlen($group);        

        $s .= $this->AddReplacement(substr($g, $l, $offset-$l), $this->callback_data);
        $s .= $group;
        $l = $offset+$strlen;
      }
      $s .= substr($g, $l);
    }
    else
      $s = $this->AddReplacement($g, $this->callback_data);
    if ($group_no !== 0)
    {
      $pre = "";
      $post = "";
      $c = count($matches);
      for ($i=1; $i<$group_no; $i++)
        $pre .= $matches[$i];
        
      for ($i=$group_no+1; $i<$c; $i++)
        $post .= $matches[$i];

      $s = $pre . $s . $post;
      if ($this->callback_data2->consume_other_groups)
      {
        $s = $this->AddReplacement($s);
      }      
    }
    return $s;
  }

  private 
  function Parse_Regex_Wrapper_Callback($matches)
  {
    return $this->AddReplacement($this->ParseRegex($matches[1]));
  }
  
  private 
  function DoSimpleRule($rule, $needle, $str)
  {
    $cb_array = array($this, 'Parse_Regex_Replace_Callback');
    $type = $rule->type;
    $regex = ($type & LUMINOUS_REGEX) > 0;
    $name = &$rule->name;
    $this->callback_data = &$rule->name;
    $this->callback_data2 = &$rule;
    
    $num_extractions_start = $this->num_extractions;
    if ($regex)
    {
      if ($this->grammar->case_insensitive === true)
        $needle .= 'i';      
      $str1 = false;
      $str1 = preg_replace_callback($needle, $cb_array, $str);      
      if ($str1 === null)
      {
        while ($this->num_extractions > $num_extractions_start)
        {
          array_pop($this->html_extractions);
          $this->num_extractions--;
        }
        trigger_error("PCRE error: " . pcre_error_decode(preg_last_error()));
      }
      else if ($str1 !== false)
        $str = $str1;
    }
    else
    {            
      $str_rep = ($this->grammar->case_insensitive)?'str_ireplace' : 
      'str_replace';        
        // need a str_replace_callback!          
        $str = $str_rep($needle, 
                        "<$name>$needle</$name>",
                        $str);
    }
    return $str;
  }
  
  
  /**
   * Deals with SimpleRules
   * \param str the input string to parse.
   * \return the input tagged according to the given simple rules.
   */ 
  private 
  function ParseRegex($str)
  {
    // in some versions of PHP this seems to be 'self::Parse_Regex_Replace_Callback'
    // in others, it's this
    $cb_array = array($this, 'Parse_Regex_Replace_Callback');
    foreach($this->local_simple_types as &$rule)
    {
      $name = &$rule->name;
      $this->callback_data = &$rule->name;
      $type = &$rule->type;
      
      $regex = ($type & LUMINOUS_REGEX) > 0;
      $literal = !isset($rule->replace_str);
      
      $needle = &$rule->text;
      
      $list = ($type & LUMINOUS_LIST) > 0;
      $str_start = $str;
      $num_extractions_start = $this->num_extractions;
      if ($list)
      {
        foreach($rule->values as $v)
        {
          if ($rule->replace_str !== null)
            $v = str_replace($rule->replace_str, $v, $needle);
          $str = $this->DoSimpleRule($rule, $v, $str);         
        }
      }
      else
        $str = $this->DoSimpleRule($rule, $needle, $str);         
    }
    return $str;
  }



  private 
  function Get_Next_Replacement($index = null)
  {
    if ($index === null)
      $index = $this->index;
    foreach($this->existing_replacements as $s)
    {
      if ($s >= $index)
        return $s;
    }
    return null;
  }

  

  private 
  function Get_Next_End($index=null)
  {
    if ($index === null)
      $index = $this->index;
    
    $i = 0;
    if ($index >= $this->last_str_index_gne)
      $i=$this->last_arr_index_gne;
    
    $num = &$this->num_ends;
    
    for($i; $i<$num; $i++)
    {
      $s = $this->ends[$i];
      if ($s >= $index)
      {
        $this->last_str_index_gne = $s;
        $this->last_arr_index_gne = $i;
        return $s;
      }
    }
    return null;
  }

  private 
  function Get_Next_Start($index=null)
  {
    if ($index === null)
      $index = $this->index;

    $i = 0;
    if ($index >= $this->last_str_index_gns)
      $i=$this->last_arr_index_gns;

    $num = count($this->starts);

    for($i; $i<$num; $i++)
    {
      $s = $this->starts[$i];
      if ($s >= $index)
      {
        $this->last_str_index_gns = $s;
        $this->last_arr_index_gns = $i;
        return $s;
      }
    }
    return null;
  }  




  private 
  function DoStartEnds()
  {

    $s_cache = array();
    $e_cache = array();
    $merge = false;
    $num=0;
    
    foreach ($this->grammar->ignore_outside as &$ignore)
    {
      
      $s = $ignore->delim_1;
      $e = $ignore->delim_2;

      $s_matches = array();
      $e_matches = array();
      if ($ignore->type & LUMINOUS_REGEX)
      {
        if ($this->grammar->case_insensitive)
        {
          $s .= 'i';
          $e .= 'i';
        }
          
        preg_match_all($s, $this->input_src, $s_matches, PREG_SET_ORDER|PREG_OFFSET_CAPTURE);
        preg_match_all($e, $this->input_src, $e_matches, PREG_SET_ORDER|PREG_OFFSET_CAPTURE);

        foreach($s_matches as $match)
        {
          $group = $match[0][0];
          $offset = $match[0][1];
          if ($ignore->type & LUMINOUS_EXCLUDE)
            $offset += strlen($group);
          $this->starts[] = $offset;
          $s_cache[$offset] = $num++;
        }
        foreach($e_matches as $match)
        {
          $group = $match[0][0];
          $offset = $match[0][1];
          if (!($ignore->type & LUMINOUS_EXCLUDE))
            $offset += strlen($group);
          if (isset($s_cache[$offset]))
          {
            // zero length match.
            unset($this->starts[$s_cache[$offset]]);
            $merge = true;
          }
          else
          {
            $this->ends[] = $offset;
            $this->ends_length[$offset] = strlen($group);
            $this->ends_excludes[$offset] = ($ignore->type & LUMINOUS_EXCLUDE) > 0;
          }
        }
      }
      else
      {
        $pos = -1;
        $strpos = ($this->grammar->case_insensitive)?'stripos' : 'strpos';        
        
        while ( ($pos = $strpos($this->input_src, $s, $pos+1)) !== false )
        {
          $this->starts[] = $pos;
          $s_cache[$pos] = $num++;
        }
        $pos=-1;
        while ( ($pos = $strpos($this->input_src, $e, $pos+1)) !== false )
        {
          if (isset($s_cache[$pos]))
          {
            // zero length match.
            unset($this->starts[$s_cache[$pos]]);
            $merge = true;
          }
          else
          {
            $this->ends[] = $pos;
            $this->ends_length[$pos] = strlen($e);
            $this->ends_excludes[$pos] = ($ignore->type & LUMINOUS_EXCLUDE) > 0;
          }
        }
      }
    }
    $this->num_ends = count($this->ends);
    if ($merge)
      $this->starts = array_merge($this->starts);

  }
  
  
  
  private 
  function SplitStartEnds()
  {
    // Here we're going to split up the <&START>(.*?)<&END>/s blocks, but
    // on largeish source files (say 200k) this may trigger the backtrack
    // limit in PCRE, so instead we do it the old fashioned way.
    // we send everything between start/end through a 'parse me'
    // function.
    $split = array();
    $p = -1;
    $last_p = 0;
    $strlen_start = strlen('<&START>');
    $strlen_end = strlen('<&END>');
    while (($p = strpos($this->output, '<&START>', $last_p)) !== false)
    {
      $split[] = substr($this->output, $last_p, $p-$last_p);
      
      // This check should be redundant.
      if (($e = strpos($this->output, '<&END>', $p)) !== false)
      {
        $lower_bound = $strlen_start + $p;
        $length = $e-$lower_bound;
        $split[] = $this->Parse_Regex_Wrapper_Callback(
            array(false, substr($this->output, $lower_bound, $length))
        );
        $p = $e + $strlen_end;
      }
      
      $last_p = $p;
    }
    $split[] = substr($this->output, $last_p);
    
    $this->output = implode('', $split);    
  }
  
  
  


  /**
   * Handles the parsing process. It's recommended to use Easy_Parse instead,
   * which wraps this function (and others).
   * \return a string which is formatted with an internal tagging spec.
   *    But the caller should not worry about that, it's only for recursion.
   *
   * \throw Exception in the event that the PCRE module fails somehow. The
   *    error is given in the exception message, but this is likely down to an
   *    exceptionally large string which is triggering the PCRE backtrack limit.
   *    The parser should survive, but the string will not by syntax highlighted
   * 
   */

    
  public 
  function Parse_Full()
  {
    $this->DoStartEnds();


    $pos = -1;
    while ( ($pos = strpos($this->input_src, "<&R_", $pos+1)) !== false)
      $this->existing_replacements[] = $pos;
    
    $parse_nothing = false;
    $parse_everything = false;
    
    // no legal start/end
    if (count($this->grammar->ignore_outside) &&
      (!count($this->starts) || !count($this->ends)
        )
      )
    {
      // Strict mode - don't parse anything
      if ($this->grammar->ignore_outside_strict)
      {
        $parse_nothing = true;
      }
    }

    if (!count($this->grammar->ignore_outside))
    {
      $parse_everything = true;
    }

    if ($parse_nothing)
    {
      $this->output = $this->input_src;
    }
    else
    {
      if ($parse_everything)
        $this->parse_all = true;
      
      $this->ParseDelimiters();

      if ($parse_everything)
      {
        $this->output = str_replace("<&START>", "", $this->output);
        $this->output = str_replace("<&END>", "", $this->output);
        $this->output = $this->Parse_Regex_Wrapper_Callback(array(0, $this->output));
      }
      else
        $this->SplitStartEnds();
    }
    
    if ($this->output === null && preg_last_error() !== PREG_NO_ERROR )
    {
      throw new Exception("PCRE error: " . pcre_error_decode(preg_last_error()));
      $this->output = $this->input;
      return $this->input;
    }
    

    if ($this->grammar->child_grammar !== null)
    {
      $highlighter = new Luminous();
      $highlighter->SetSource($this->output);
      $highlighter->SetGrammar($this->grammar->child_grammar);      
      $highlighter->SetExtractionsOffset(($this->num_extractions+$this->extractions_offset));
      $this->output = $highlighter->Parse_Full();
    }
    
    $this->DoReplacements();

    return $this->output;
  }


  private 
  function Replacements_cb(&$matches)
  {
    $i = $matches[1];

    if ($this->extractions_offset > 0)
    {
      if (isset($this->html_extractions[$i]))
      {
        $this->num_extractions--;
        return $this->html_extractions[$i];
      }
      else return $matches[0];
    }
    
    else
    {
      if (isset($this->html_extractions[$i]))
      {        
        $this->num_extractions--;
        return $this->html_extractions[$i];
      }
      else return $matches[0];
    }
  }
  
  

  
  private 
  function DoReplacements()
  {

    while($this->num_extractions > 0)
    {
      $num_start = $this->num_extractions;
      $this->output = preg_replace_callback("/<&R_([0-9]+)>/",
        array($this, "Replacements_cb"),  $this->output);
        
      $num_end = $this->num_extractions;  
      if ($num_start == $num_end)
      {
        trigger_error("The parser was unable to perform all substitutions 
        ($num_end are missing). If this is the only error, please ensure your 
          rules do not target the parser's internal tagging system. 
          See the doxygen API docs for details on what you've probably done wrong.
          Output is probably malformed");
          
        return $this->output;
      }
        
    }
    
    return $this->output;
  }

  /** Gets the most recent output string as calculated by Parse_Full() */
  
  public 
  function GetOutput()
  {
    return $this->output;
  }
  


  /**
   * Recommended method to complete the entire parsing process. Takes in a 
   * source string and its language or gramamr and returns to you a formatted 
   * HTML string (we hope).
   * 
   * \param source_string: The source to parse, as a string
   * \param grammar The LuminousGrammar to apply to the source.
   * \return return A string which is 'tagged' by Luminous's spec. This should
   * then be given to an instance of LuminousFormatter to be turned into 
   * something more universal.
   * \throw Exception if no suitable grammar is given.
   * 
  */

  public 
  function Easy_Parse($source_string, LuminousGrammar $grammar)
  {
    if (!is_subclass_of($grammar, 'LuminousGrammar'))
      throw new Exception("Bad grammar");
    $this->SetSource($source_string);
    
    if (!$this->pre_escaped)      
      $this->EscapeInput();
    
    $this->SetGrammar($grammar);
    
    
    $this->Parse_Full();
    if ($this->append_newline)
    {
      
      $pos = strrpos($this->output, "\n");
      if ($pos !== false)
      {
        $s1 = substr($this->output, 0, $pos);
        $s2 = (($pos+1)<strlen($this->output))? substr($this->output, $pos+1) : "";
        $this->output = $s1 . $s2;
      }
    }
    $this->output = preg_replace("/(<LANG_.*?)\n/s", "$1", $this->output);
    
    return $this->output;
  }
}

